我最近好高产啊\tiny 我最近好高产啊我最近好高产啊
今天我们来学习一种强大的算法——高斯消元
> 目录
>
>
> > 1.简介
> >
> >
> > 2.核心思想
> >
> >
> > 3.算法流程
> >
> >
> > 4.代码实现
> >
> >
> > 5.初级应用
> >
> >
> > 6.进阶应用 也没多进阶
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 1. 简介
高斯消元法是一种用于求解nnn元一次方程组的经典算法。它的核心思想是通过加减消元法来求解方程。
PART 2. 核心思想
高斯消元法的核心思想是通过加减消元法来求解线性方程。
PART 3. 算法流程
我们首先从二元一次方程组来入手，二元一次方程组主要有两种方法：加减消元法和代入消元法。我们主要讲解加减消元法。
举个例子：
{5x+3y=1002x+2y=50\begin{cases} 5x + 3y = 100 \\ 2x + 2y = 50 \end{cases} {5x+3y=1002x+2y=50
我们通过一式、二式同时乘一定的数值来消去xxx，变形为：
{10x+6y=20010x+10y=250\begin{cases} 10x + 6y = 200 \\ 10x + 10y = 250 \end{cases} {10x+6y=20010x+10y=250
于是就可以二式减去一式，得
4y=504y=50 4y=50
于是
y=252y=\frac{25}{2} y=225
代回去，得
{x=252y=252\begin{cases} x = \frac{25}{2} \\ y = \frac{25}{2} \end{cases} {x=225 y=225
于是，我们可以把加减消元法扩展至nnn的情况
注意此方程
{a1x1+a2x2+⋯+anxn=b1an+1x1+an+2x2+⋯+a2nxn=b2…an2−n+1x1+an2−n+2x2+⋯+an2xn=bn\begin{cases} a_1x_1+a_2x_2+\dots+a_nx_n=b_1 \\ a_{n+1}x_1+a_{n+2}x_2+\dots+a_{2n}x_n=b_2 \\ \dots\\ a_{n^2-n+1}x_1+a_{n^2-n+2}x_2+\dots+a_{n^2}x_n=b_n \end{cases} ⎩⎨⎧ a1 x1 +a2 x2 +⋯+an xn =b1 an+1 x1 +an+2 x2 +⋯+a2n xn =b2
…an2−n+1 x1 +an2−n+2 x2 +⋯+an2 xn =bn
或者写作
{a1,1x1+a1,2x2+⋯+a1,nxn=b1a2,1x1+a2,2x2+⋯+a2,nxn=b2…an,1x1+an,2x2+⋯+an,nxn=bn\begin{cases} a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n=b_1 \\ a_{2,1}x_1+a_{2,2}x_2+\dots+a_{2,n}x_n=b_2 \\ \dots\\ a_{n,1}x_1+a_{n,2}x_2+\dots+a_{n,n}x_n=b_n \end{cases} ⎩⎨⎧ a1,1 x1 +a1,2 x2 +⋯+a1,n xn =b1 a2,1 x1 +a2,2 x2
+⋯+a2,n xn =b2 …an,1 x1 +an,2 x2 +⋯+an,n xn =bn
* 用一式、二式消掉x1x_1x1
* 用二式、三式消掉x1x_1x1
…\dots…
* 用最后两式消掉x1x_1x1
于是，我们可以得到n−1n-1n−1个方程，其中有n−1n-1n−1个未知数。
再重复消元这一步骤，消到n−2n-2n−2个元、n−3n-3n−3个元、…\dots… 、最终消到111元111次，方程就解出来了。
这就是高斯消元的主要步骤。
PART 4. 代码实现
高斯消元的代码是基于矩阵的。
还是这个方程：
{a1,1x1+a1,2x2+⋯+a1,nxn=b1a2,1x1+a2,2x2+⋯+a2,nxn=b2…an,1x1+an,2x2+⋯+an,nxn=bn\begin{cases} a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n=b_1 \\ a_{2,1}x_1+a_{2,2}x_2+\dots+a_{2,n}x_n=b_2 \\ \dots\\ a_{n,1}x_1+a_{n,2}x_2+\dots+a_{n,n}x_n=b_n \end{cases} ⎩⎨⎧ a1,1 x1 +a1,2 x2 +⋯+a1,n xn =b1 a2,1 x1 +a2,2 x2
+⋯+a2,n xn =b2 …an,1 x1 +an,2 x2 +⋯+an,n xn =bn
在代码中，会表示为如下矩阵：
(a1,1,a1,2,…,a1,n,b1a2,1,a2,2,…,a2,n,b2…an,1,an,2,…,an,n,bn)\begin{pmatrix} a_{1,1},a_{1,2},\dots,a_{1,n},\color{red}{b_1} \\ a_{2,1},a_{2,2},\dots,a_{2,n},\color{red}{b_2} \\ \dots\\ a_{n,1},a_{n,2},\dots,a_{n,n},\color{red}{b_n} \end{pmatrix} a1,1 ,a1,2 ,…,a1,n ,b1 a2,1 ,a2,2 ,…,a2,n ,b2 …an,1
,an,2 ,…,an,n ,bn
既然表示出来了，余下就很简单了，分为两个部分：
* 消元
* 回代（可以递归实现）
> 要注意一些代码的细节，高斯消元的代码还是比较难写的
PART 5. 初级应用
给出一道例题
这是一道模板题，直接给出代码。
PART 6. 进阶应用
这是一道模板题
逆元+高斯消元即可，代码请自行完成
OK也是刷新创作计划的最短记录了
@AC君求精
